DSA數位簽章算法

之前介紹了運用RSA公鑰演算法來運用的RSA數位簽章算法,今天要介紹的則是用離散對數和模運算的數位簽章算法
DSA數位簽章算法是在做數位簽章時的聯邦資訊處理標準之一,也有加上橢圓曲線的ECDSA演算法

如何簽章

首先要先生成合法安全的參數

1.和RSA簽章一樣要有一個雜湊函式,常見的為SHA-2
2.選擇金鑰長度L,現在推薦2048位元
3.選擇模數長度N,N<L,且N<H的輸出,規定L為2048下N為224或256
4.選擇等級為N位元的質數q
5.選擇等級為L位元的質數p,須滿足(p-1)為q的倍數
6.從{2,3...(p-2)}中選擇一個數h
7.計算g=h^(p-1)/q mod p,g不能等於1
8.參數(g、p、q)公開

再來是金鑰

1.在{1,2...(q-1)}中選一個數e
2.計算私鑰d=g^e mod p

簽章

對於訊息pt和其雜湊值hash_value
1.在{1...(q-1)}隨機選一個數k
2.計算r=(g^k mod p)mod q,如果r==0,重新選擇k
3.計算s=(k^(-1)⋅(hash_value+dr)) mod q,s==0,重新選擇k
4.把r和s組合成(r,s),組合後就是簽章
5.pt、簽章與其使用雜湊函式也送出

驗章

1.計算w=s^(-1) mod q
2.計算a=hash_value⋅w mod q
3.計算b=r⋅w mod q
4.計算v=(g^a⋅e^b mod p)mod q
5.如果v==r簽章有效

注意

1.簽章後一樣要做加密再送出
2.隨機選擇的k必須保密,又稱隨機秘密
3.隨機秘密k必須真的很隨機,如果重複使用會洩漏私鑰
4.計算上比RSA複雜很多,好算的比較香